
DependencyGraph = Concentre.Class(Object, {
	vertices : [],
	changedVertices: [],
	vertexLookupHash: {},
	count: 0,	

	initialize: function(model) {
	
		this.vertices = [];
		this.changedVertices = [];
		this.vertexLookupHash = {};
		this.count = 0;
		this.model = model;
	},

	addVertex: function (node, property, context, xpath) {
		assert(node     != null);
 		assert(property != null);
		
  		var vertex = this.getVertex(node, property);
    
  		if (vertex == null) {
    		var hash  = node.nodeName + "." + property;
						
			vertex = new Vertex(this, this.count++ , node, property, context, xpath);
   			vertex.touch();
   		
   			this.vertices.push(vertex);
  			  
    		// Add the vertex to the lookup hash table.
    		if (!this.vertexLookupHash[hash]) {
      			this.vertexLookupHash[hash] = [];
   			 }
    
    		this.vertexLookupHash[hash].push(vertex);
  		} 
  		else {
    		if (property != "text") {
    	    	throw new Exception("Duplicate model item property: " + property);
    		}
  		}
  
 	 return vertex; 
	},

	getVertex:function(node, property) {
		var vertices = this.vertexLookupHash[node.nodeName + "." + property];
		if (!vertices) return null;  
		
		for (var i=vertices.length; --i>=0;) { 
    		vertex= vertices[i]; 
    		switch (true) {
    			case !vertex: 
    			case vertex.property != property:
					continue;
				case vertex.node === node:
					return vertex;
			}
  		}
  
 	 	return null;
	},

	resetChangedVertices: function() {
  		for (var i=this.changedVertices.length;--i>=0;) {
    		this.changedVertices[i].hasChanged = false;
 	 	}
 
  		this.changedVertices = [];
	},

	getPertinentSubGraph: function() {
  		var subGraph = new DependencyGraph(this.model);
  		subGraph.addSuperGraphVertices(this.changedVertices);
  		return subGraph;
	},

	addSuperGraphVertices: function(vertices) {
		
  		for (var i=vertices.length; --i>=0; ) {
    		var vertex = vertices[i];
        	
   			if (this.vertices[vertex.index] != null) {
      			continue;
    		}
						
 			var parentClone = vertex.clone();
    		this.vertices[vertex.index] = parentClone;
    		this.count++;
			
    		this.addSuperGraphVertices(vertex.dependents);

			
    		for (var j = vertex.dependents.length; --j >=0;) {
      			var dependent      = vertex.dependents[j];
	 			var dependentClone = this.vertices[dependent.index];
       			
       			dependentClone.dependsOn(parentClone);
   	 		}
  		} 
	},

	toString : function() {
 		
 		
 		var str= '', vertex, deps;
   		
   		for (var i = this.vertices.length; --i >=0; ) {
 			vertex = this.vertices[i];
 			if (!vertex) continue;
 			
 			deps = [];
    		
    		str += "#" + i + ": " + vertex + " -- in: " + vertex.inDegree + ", out: [";
    		
    		for (var j = vertex.dependents.length; --j>=0; ) {
				if (vertex.dependents[j]) {
					deps.push(j+':'+vertex.dependents[j]);
				}
    		}
    		str += deps.join(',') + "]\n";
  		}

 	 return str;
	}
});	



Vertex = Concentre.Class(Object,{

	initialize: function(graph, index, node, property, context, xpath) {
  assert(graph != null);
  assert(node  != null);
  
  this.graph      = graph;
  this.index      = index;
                 
  this.node       = node;
  this.property   = property;
  this.context    = context;
  this.xpath      = xpath;
  this.value      = null;
  
  this.dependents = [];
  this.inDegree   = 0;
  
  this.hasChanged = false;
  this.controls   = [];
	},

	clone:	function() {
 		var vertex = new Vertex(
                 this.graph,
                 this.index,
                 this.node,
                 this.property,
                 this.context,
                 this.xpath
               );
  
  		vertex.contextNode = this.contextNode;
  		vertex.hasChanged  = this.hasChanged;
  
 		return vertex;
	},

	dependsOn: function(vertex) {
  		vertex.dependents.push(this);
		++this.inDegree;
	},

	touch: function() {
 		if (!this.hasChanged) {
    		this.hasChanged = true;
   			this.graph.changedVertices.push(this);
  		}
	},

	getValue:function() {
		if (this.property == "text") {
    
    		switch (this.node.nodeType) {
     			case 1: // Element
        			for (var textNode = this.node.firstChild; textNode != null; textNode = textNode.nextSibling) {
          				if (textNode.nodeType == 3) {
            				return textNode.nodeValue;
          				}
        			}
          		case 9:// Document
       				return "";
	      		case 2: // Attribute
    	  		case 3: // Text node
    	  		case 4: // CDATA node
    	  			return this.node.nodeValue;
	      		default:
    				throw new Exception("Unexpected vertex node: " + this.node.nodeName + " (" + this.node.nodeType + ")");
    		}
 		} else {
 			return this.value;
  		}
	},

	setValue: function(value) {
		if (value == this.getValue()) {
   			// Commented out this line. Why is it here?
   			// Please comment why this is needed if uncommenting...
    		// this.graph.changedVertices.push(this);
		    return;
  		}
  
 		if (this.property == "text") {
   			switch (this.node.nodeType) {
      			case 1: // Element
        			// Look for the first child text node.
        			for (var textNode = this.node.firstChild; textNode != null; textNode = textNode.nextSibling) {
          				if (textNode.nodeType == 3) {
            				break;
          				}
        			}
        
        			if (textNode != null) {
          				textNode.nodeValue = value;
        			} else if (value != "") {
          				this.node.insertBefore(this.node.ownerDocument.createTextNode(value), this.node.firstChild);
        			}
       				
       				break;
   			   case 2: // Attribute
      		   case 3: // Text node
      		   case 4: // CDATA node
      		   		this.node.nodeValue = value;
        			break;
			   default:
        			throw new Exception(this.node, "Invalid node in dependency graph: " + this.node.nodeName + " (" + this.node.nodeType + ")");
   	 		}
  		} else {
    		this.value = value;
  		}
 		
 		this.touch();
	},


	refresh: function() {
		var value = this.getValue();

  		for (var i=this.controls.length; --i>=0;) {	
    		this.controls[i].setProperty(this.property, value);
  		}
	},

	toString:function() {
 		var prefix   = (this.node.nodeType == 2) ? "@" : "";
  		var name     =  this.node.nodeName;
  		var property =  this.property;

  		// Code is a huge bottleneck. Commented out for efficiency.
  		//
  		// if (this.node.nodeType == 1 || this.node.nodeType == 2) {
  		//   var size     = new XPath("count(../" + prefix + name + ")")       .evaluate(this.node);
  		//   var position = new XPath("count(preceding-sibling::" + name + ")").evaluate(this.node) + 1;
  		//   
  		//   if (size > 1) {
  		//     name += "[" + position + "]";
  		//   }
  		// }
  
  		return prefix + name + "." + property;
  	}
});


	
